package com.xj.algorithm.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 存在重复元素
 */
public class L217_数组中是否存在重复元素 {

    /**
     *给定一个整数数组，判断是否存在重复元素。
     *
     * 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
     *
     * 示例 1:
     *
     * 输入: [1,2,3,1]
     * 输出: true
     * 示例 2:
     *
     * 输入: [1,2,3,4]
     * 输出: false
     * 示例 3:
     *
     * 输入: [1,1,1,3,3,4,3,2,4,2]
     * 输出: true
     */

    public static void main(String[] args) {
        int[] nums=new int[]{1,2,3,1};
        System.out.println(containsDuplicateOffice(nums));

        int[] nums2=new int[]{1,2,3,4};
        System.out.println(containsDuplicateOffice(nums2));

        int[] nums3=new int[]{1,1,1,3,3,4,3,2,4,2};
        System.out.println(containsDuplicateOffice(nums3));
    }

    //自己的解法：hash表
    public static boolean containsDuplicate(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int value:nums){
            if(map.containsKey(value)){
                return true;
            }
            map.put(value,value);
        }
        return false;
    }

    //官方解法：排序后相邻值是否相等
    public static boolean containsDuplicateOffice(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; ++i) {
            if (nums[i] == nums[i + 1]) return true;
        }
        return false;
    }
}